/// @tags: DP by Range
#include <algorithm>
#include <cstdio>
#include <iostream>

using std::cin, std::cout, std::endl;

namespace BlueQuantum {

constexpr int maxn = 5e1 + 2, maxm = 4e3 + 2;

int n, m;
int a[maxm], b[maxm], c[maxm], cc[maxm], ans[maxn];
int f[maxn][maxn][maxm], cnt[maxn][maxm], pos[maxn][maxn][maxm], pri[maxn][maxn][maxm];

void solve(int l, int r, int k) {
  if (l > r) return;
  int p = pos[l][r][k = pri[l][r][k]];
  ans[p] = cc[k];
  solve(l, p - 1, k), solve(p + 1, r, k);
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> a[i] >> b[i] >> c[i];
    cc[i] = c[i];
  }
  std::sort(cc + 1, cc + m + 1);
  int size = std::unique(cc + 1, cc + m + 1) - cc - 1;
  for (int i = 1; i <= m; ++i) c[i] = std::lower_bound(cc + 1, cc + size + 1, c[i]) - cc;
  for (int len = 1; len <= n; ++len) {
    for (int l = 1; l + len - 1 <= n; ++l) {
      int r = l + len - 1;
      for (int i = l; i <= r; ++i)
        for (int j = 1; j <= size; ++j) cnt[i][j] = 0;
      for (int i = 1; i <= m; ++i)
        if (l <= a[i] && b[i] <= r)
          for (int j = a[i]; j <= b[i]; ++j) cnt[j][c[i]]++;
      for (int i = l; i <= r; ++i)
        for (int j = size - 1; j; --j) cnt[i][j] += cnt[i][j + 1];
      for (int k = size; k; --k) {
        for (int i = l; i <= r; ++i) {
          int val = f[l][i - 1][k] + f[i + 1][r][k] + cnt[i][k] * cc[k];
          if (val >= f[l][r][k]) {
            f[l][r][k] = val;
            pos[l][r][k] = i;
          }
        }
        if (f[l][r][k] >= f[l][r][k + 1]) {
          pri[l][r][k] = k;
        } else {
          f[l][r][k] = f[l][r][k + 1];
          pos[l][r][k] = pos[l][r][k + 1];
          pri[l][r][k] = pri[l][r][k + 1];
        }
      }
    }
  }
  cout << f[1][n][1] << endl;
  solve(1, n, 1);
  for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P3592 [POI2015] MYJ.in", "r", stdin);
  freopen("P3592 [POI2015] MYJ.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}